from typing import List


class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        ans = []  # 存储最终结果
        # 计数数组，索引0-100对应实际值-50到50
        count = [0] * 101  # nums[i] ∈ [-50, 50] → mapped to [0, 100]

        for i in range(n):
            # 将当前数字加入窗口（+50将值映射到0-100范围）
            count[nums[i] + 50] += 1

            # 当窗口大小达到k时开始计算
            if i >= k - 1:
                pos = 0  # 用于累计当前已遍历的数字数量
                # 遍历计数数组寻找第x小的数
                for j in range(101):
                    pos += count[j]
                    # 当累计数量达到x时，找到第x小的数
                    if pos >= x:
                        beauty = j - 50  # 将映射的值转换回原始值
                        # 根据题目要求，只有负数才保留，否则取0
                        ans.append(beauty if beauty < 0 else 0)
                        break

                # 滑动窗口左边界右移，将离开窗口的数字从计数中移除
                count[nums[i - k + 1] + 50] -= 1
        return ans